
// LCR 094.分割回文串II
class Solution {
public:
    int minCut(string s) {
        // 使用动态规划来实现
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));  // dp[i][j] 表示[j , i]是否是回文串

        for(int i = 0 ;i < n ; i++)
        {
            for(int j = 0 ; j <= i ; j++)
            {
                if(s[i] == s[j] && (i == j || j + 1 == i || dp[i - 1][j + 1]))
                    dp[i][j] = true;
            }
        } 
        
        vector<int> mem(n,-1);
        function<int(int)> dfs = [&](int pos)
        {
            if(pos == n ) return -1;
            if(mem[pos] != -1) return mem[pos];

            int step = dfs(pos + 1) + 1;
            for(int k = pos + 1; k < n ; k++)
                if(dp[k][pos]) step = min(step , dfs(k + 1) + 1);
            mem[pos] = step;
            return step;
        };

        return dfs(0);
    }
};